# 直接利用质因子分解求解单个的欧拉函数
def euler_phi(n):
    ans=n
    m=int(n**0.5)  # 如果一个数有质因子，则质因子不大于 n**0.5，因为当前n最大的质因子就是 根号n
    for i in range(2,m+1):
        # i是质因子，也是质数， 因为 唯一分解定理中，存储的数全部是质数
        if n%i==0:
            ans=ans//i*(i-1)  # 由公式 分子分母通分 转换得来
            while n%i==0:
                n=n//i
    # 还有剩余 或者 是n是质数，没有质因子
    if n>1:
        ans=ans//n*(n-1)
    return ans
print(euler_phi(8),8-4)

# 利用线性筛，求解多个的 欧拉函数
def get_prime(n):
    vis=[0]*(n+1)
    prime=[]
    phi=[0]*(n+1)
    phi[1]=1
    # 从2-n 遍历所有数字，找到第一个未标记的数字，即为质数
    for i in range(2,n+1):
        if vis[i]==0:
            prime.append(i)
            phi[i]=i-1    # 欧拉函数的定义
        for x in prime:
            if i*x>n:
                break
            vis[i*x]=1
            if i%x==0:
                phi[i*x]=phi[i]*x  # 欧拉函数的性质，当 i 是 x 的倍数时，有 φ(i * x) = φ(i) * x,例如：i=4时，phi[i*x]=phi[4*2]=phi[4]*phi[2]
                break
            phi[i*x]=phi[i]*phi[x]  # 欧拉函数定义： 互质使用 积性函数，例如：i=2时，phi[i*x]=phi[2*2]=phi[2]*phi[2]
    return prime,phi
prime,phi=get_prime(30)
print(prime)
print(phi)

